﻿namespace AlgorithmInterview.Chapter01._02;

/// <summary>
/// 方法一：顺序删除
/// </summary>
public class Test01
{
    /// <summary>
    /// 对带头结点的无序单链表删除重复的结点
    /// </summary>
    /// <param name="head"></param>
    public static void RemoveDup(LNode head)
    {
        if (head == null || head.next == null)
            return;
        LNode outerCur = head.next; // 外层循环指针，指向链表第一个结点
        LNode innerCur = null; // 内层循环用来遍历outerCur后面的结点
        LNode innerPre = null; // innerCur的前驱结点
        for (; outerCur != null; outerCur = outerCur.next)
        {
            for (innerCur = outerCur.next, innerPre = outerCur; innerCur != null;)
            {
                // 找到重复的结点并删除
                if (outerCur.data == innerCur.data)
                {
                    innerPre.next = innerCur.next;
                    innerCur = innerCur.next;
                }
                else
                {
                    innerPre = innerCur;
                    innerCur = innerCur.next;
                }
            }
        }
    }
}